import collections


class Solution(object):
    def tallestBillboard(self, rods):
        n = len(rods)
        DP = collections.defaultdict(int)
        DP[rods[0]] = 0
        DP[0] = 0
        for i in range(1,n):
            next_DP = collections.defaultdict(int)
            for t in DP:
                next_DP[t + rods[i]] = max(DP[t], next_DP[t + rods[i]])
                if rods[i] < t:
                    next_DP[t - rods[i]] = max(DP[t] + rods[i], next_DP[t - rods[i]])
                else:
                    next_DP[rods[i] - t] = max(next_DP[rods[i] - t], DP[t] + t)
                next_DP[t] = max(next_DP[t], DP[t])
            DP = next_DP
        return DP[0]


data = Solution()
rods = [1, 2]
print(data.tallestBillboard(rods))
